The field of the invention is the automated design of complex structures, such as electrical circuits; more particularly, the present invention relates to designing complex structures, such as electrical circuits, using computer-implemented genetic algorithms.
The automated design of complex structures that satisfy a designer""s requirements is a challenging task that is ordinarily thought to require human intelligence.
Electrical engineers are often called upon to design circuits that satisfy certain design goals or requirements. Electrical circuits consist of a wide variety of different types of components, including resistors, capacitors, inductors, diodes, transistors, transformers, and energy sources. The individual components of an electrical circuit are arranged in a particular xe2x80x9ctopologyxe2x80x9d to form a circuit.
Various types of components may be inserted at each location within the circuit""s topological arrangement. In addition, each component is further specified (xe2x80x9csizedxe2x80x9d) by a set of component values (typically numerical). A complete specification of an electrical circuit includes its topology, the choice of component types to be inserted at each location within the topology, and the sizing of all of its components.
In designing a circuit, the goal is to attain certain desired values of one or more observable quantities (e.g., an observed pattern of voltages at certain times or at certain frequencies at a certain probe point in the circuit). Often there are one or more additional considerations (e.g., number of components in the circuit, cost of the components, etc.).
This application is a continuation of U.S. patent application Ser. No. 08/603,648, entitled xe2x80x9cMethod and Apparatus for Automated Design of Complex Structures using Genetic Programming,xe2x80x9d filed Feb. 20, 1996.
Similarly, mechanical and civil engineers are often called upon to design physical structures that satisfy certain design goals or requirements. Physical structures, like electrical circuits, consist of a variety of different types of components. These individual components may be arranged in a particular topology to form the overall complex physical structure. Various types of components may be inserted at each location within the topological arrangement. Each component in the overall structure may be further specified by a set of component values (typically numerical). For example, a mechanical engineer may want to design as truss consisting of components such as rigid load-supporting metallic beams and load-supporting flexible cables. The design goals may be to support a particular load or loads and of satisfying a requirement that the stress on each bar or cable is not so great as to cause the rigid bar or flexible cable to break. Finally, there may be an additional design goal that the entire physical structure meets some cost requirement, such as minimizing the total weight of the material contained in the truss. In order to design the desired truss, the designer must create an appropriate topological arrangement of components (i.e., the number of components and how they are joined), choose component types (i.e., rigid beams or flexible cables) to insert into the topological arrangement, and choose appropriate numerical values (i.e., their thickness) for each of the components.
Both the above electrical and mechanical design problems and many other design problems from many other fields share the common feature of requiring the designer to create an appropriate topological arrangement of components, to choose component types to insert into the topological arrangement, and to choose appropriate numerical values for each of the components in the overall complex structure.
In nature, biological entities exhibit a wide variety of structures that survive and prosper in various environments. Nature""s methods for designing biological entities to meet the requirements of their natural environment provides a useful model for designing complex structures.
Most structures and behaviors in living things are the consequence of the actions and interactions of proteins. In fact, proteins are responsible for such a wide variety of biological structures and behaviors that it can be said that the structure and functions of living organisms are primarily determined by proteins. Proteins are polypeptide molecules composed of sequences of amino acids. There are 20 amino acid residues (denoted by the letters A, C, D, E, F, G, H, I, K, L, M, N, P, Q, R, S, T, V, W, and Y) from which protein molecules are constructed. Protein molecules are, in turn, made up of an average of about 300 such amino acid residues (with large proteins containing thousands of amino acid residues). Simple bacteria sustain life with as few as 1,800 different proteins while humans have an estimated 100,000 proteins.
Proteins are manufactured in accordance with instructions and information contained in the chromosomal DNA of the organism. DNA (deoxyribonucleic acid) is a long thread-like biological molecule that has the ability to carry hereditary information and the ability to serve as a model for the production of replicas of itself. All known life forms on this planet (including bacteria, fungi, plants, animals, and humans) are based on the DNA molecule. In nature, a gene is the basic functional unit by which hereditary information is passed from parents to offspring. Genes appear at particular places along molecules of deoxyribonucleic acid (DNA).
The so-called xe2x80x9cgenetic codexe2x80x9d involving the DNA molecule consists of long strings (sequences) of 4 possible values that can appear at the various loci along the DNA molecule. For DNA, the 4 possible values refer to 4 xe2x80x9cbasesxe2x80x9d named adenine, guanine, cytosine, and thymine (usually abbreviated as A, G, C, and T, respectively). Thus, the xe2x80x9cgenetic codexe2x80x9d in DNA consists of long strings such as CTCGACGGT. When living cells reproduce, the genetic code in DNA is read. Sub-sequences (called xe2x80x9ccodonsxe2x80x9d) consisting of 3 DNA bases specify one of 20 amino acids. Thus, the genetic code is used to specify and control the building of proteins from the information and instructions contained in the DNA molecule.
Organisms consist of living cells, each containing thousands of interacting proteins, spend their lives attempting to deal with their environment. Some organisms do better than others in dealing with their environment. In particular, some organisms survive to the age of reproduction and can then thereby pass on their genetic make-up (i.e., their genes) to their offspring. Natural selection is the process by which organisms whose traits facilitate survival to the age of reproduction pass on all or part of their genetic make-up to offspring (Darwin 1859). Over a period of time and many generations, the population as a whole evolves so that the chromosome strings in the individuals in the surviving population perpetuate traits that contribute to the survival of the organism in its environment. That is, the natural selection process tends to evolve, over a period of time, structures that are designed so as to deal effectively with their environment.
Genetic Algorithms
A genetic algorithm provides a method of improving a given set of objects. The processes of natural selection and survival of the fittest provide a theoretical base for the genetic algorithm. Adaptation in Artificial and Natural Systems, by Professor John H. Holland (1975), summarizes and presents an overall mathematical theory of adaptation for both natural and artificial systems. A key part of Holland""s book described a xe2x80x9cgenetic algorithmxe2x80x9d patterned after nature""s methods for biological adaptation. In later work, Holland (1986) described a classifier system that employed a genetic algorithm and a bucket brigade algorithm to solve problems. U.S. Pat. No. 4,697,242 (Holland et al.) and U.S. Pat. No. 4,881,178 (Holland et al.) describe classifier systems that use fixed length binary strings in conjunction with a genetic algorithm.
Genetic Programming
xe2x80x9cGenetic programmingxe2x80x9d (also called the xe2x80x9cnon-linear genetic algorithmxe2x80x9d or the xe2x80x9chierarchical genetic algorithmxe2x80x9d in previous years) is described in the book entitled Genetic Programming: On the Programming of Computers by Means of Natural Selection (Koza 1992), the book entitled Genetic Programming II: Automatic Discovery of Reusable Programs (Koza 1992) and in U.S. Pat. Nos. 4,935,877, 5,136,686, 5,148,513, and 5,343,554.
Genetic programming is referred to as xe2x80x9cnon-linearxe2x80x9d or xe2x80x9chierarchicalxe2x80x9d because the original genetic algorithm described by Holland in 1975 operated on linear strings of characters (resembling chromosomes in nature), whereas genetic programming operates on hierarchical program trees of various sizes and shapes. Genetic programming is capable of evolving computer programs that solve, or approximately solve, a variety of problems from a variety of fields. Genetic programming starts with a primordial ooze of randomly generated programs composed of the available programmatic ingredients and then applies the principles of animal husbandry to breed a new (and often improved) population of programs. The breeding is done in a domain-independent way using the Darwinian principle of survival of the fittest, an analog of the naturally-occurring genetic operation of crossover (sexual recombination), and occasional mutation. The crossover operation is designed to create syntactically valid offspring programs (given closure amongst the set of ingredients). Genetic programming combines the expressive high-level symbolic representations of computer programs with the near-optimal efficiency of learning associated with Holland""s genetic algorithm. A program that solves (or approximately solves) a given problem often emerges from this process.
As demonstrated in the book, Genetic Programming II: Automatic Discovery of Reusable Programs (Koza 1994) genetic programming can evolve multi-part programs consisting of a main program and one or more reusable, parameterized, hierarchically-called subprograms (called automatically defined functions or ADFs).
Genetic programming breeds computer programs to solve problems by executing the following three steps:
(1) Generate an initial population of random compositions of the functions and terminals of the problem (i.e., computer programs).
(2) Iteratively perform the following substeps until the termination criterion has been satisfied:
(A) Execute each program in the population and assign it a fitness value using the fitness measure.
(B) Create a new population of computer programs by applying the following operations. The operations are applied to computer program(s) chosen from the population with a probability based on fitness.
(i) Reproduction: Copy an existing program to the new population.
(ii) Crossover: Create new offspring program(s) for the new population by recombining randomly chosen parts of two existing programs.
(iii) Mutation: Create one new offspring program for the new population by randomly mutating a randomly chosen part of one existing program.
(3) The program that is identified by the method of result designation (e.g., the best-so-far individual) is designated as the result of the genetic algorithm for the run. This result may be a solution (or an approximate solution) to the problem.
Other genetic programming processes may utilize additional operations such as xe2x80x9cpermutation,xe2x80x9d xe2x80x9cdefine building blockxe2x80x9d (also called xe2x80x9cencapsulationxe2x80x9d), or the architecture-altering operations mentioned later.
Cellular Encoding of Neural Networks
A neural network is a structure consisting of one or more neural processing units (neurons). A neural network can be represented by a line-labeled, point-labeled, directed graph. The points of the graph are either neural processing units within the neural network, input points, or output points. The lines are labeled with numerical weights to represent the weighted connections between two points. The neural processing units are labeled with two numbers indicating the threshold and the bias of the processing unit.
The only type of component in a neural network is a neural processing unit. Neural networks are dynamical systems in the sense that the state of the network at a future time depends on the state of the network at the current time and the inputs to the network at the current time. There is a directional flow of information in neural networks. In feedforward neural networks, information flows from the inputs to the network, through the neurons, to the outputs of the network without any cycles within the directed graph representing the network. In recurrent neural networks, the output at a particular instant in time of one or more individual neurons in the network may be sent back to become the input at a future time of another neural processing unit so as to create a cycle within the directed graph representing the network.
The conventional genetic algorithm operating on fixed-length character strings provides a way to search the highly nonlinear multidimensional search space of weight vectors to discover the numerical weights for the connections as well as the thresholds and biases of a neural network; however, the architecture of the neural network must be specified in advance (Schaffer and Whitley 1992). The difficulty in automating the discovery of the architecture using genetic methods has centered on finding a malleable representation for the line-labeled, point-labeled, graph representing the neural network that is receptive to the kinds of operations performed by the genetic algoritam.
Some early work applied genetic programming to the problem of discovering both the architecture and weights of a neural network using the xe2x80x9cdefine building blockxe2x80x9d (also called xe2x80x9cencapsulationxe2x80x9d) operation of genetic programming (Koza and Rice 1991). The book The Algorithmic Beauty of Plants describes Lindenmayer systems (L-systems) and grammar rewrite rules. These systems provide a way to develop a complex pattern by applying rewriting rules to an initial (or embryonic) pattern.
In his Cellular Encoding of Genetic Neural Networks, Frederic Gruau (1992a) described a technique, called cellular encoding, in which genetic programming is used to concurrently evolve the architecture of a neural network, along with the weights, thresholds, and biases of the individual neurons in the neural network. In this technique, each individual program tree in the population is a specification for developing a complete neural network from a very simple neural network consisting of a single neuron. Genetic programming is applied to populations of these network-constructing program trees in order to evolve a neural network capable of solving the problem at hand. See also Gruau 1992b, 1993, 1994a, 1994b.
In cellular encoding, each program tree is a composition of constructing functions. The program tree is the genotype and the neural network constructed in accordance with the tree""s instructions is the phenotype. The fitness of an individual program tree in the population is measured by how well the neural network that is constructed in accordance with the instructions contained in the program tree performs the desired task. This is typically accomplished by exposing the neural network to all (or a large sampling) of possible combinations of inputs and testing whether the output(s) of the neural network matches the correct output(s) for the particular combination of inputs. For many problems, fitness is computed from the number of correct and incorrect output(s) from the neural network. Genetic programming then breeds the population of program trees using the usual genetic operations of Darwinian reproduction, crossover, and mutation.
In cellular encoding, the construction process for a neural network starts from a neural network consisting of a single neuron. This neuron has a threshold of 0; its bias is 0; its input is connected to all of the network""s input nodes with connections with weights of +1; its output is connected to all of the network""s output nodes. The functions in the program tree then specify how to grow this neuron into the full neural network. Certain context-free functions permit a particular neuron to be subdivided in a parallel or sequential manner. Other functions can change the threshold of a neuron, the weight of a connection, or the bias on a neuron.
The SPICE Simulator for Electrical Circuits
In many fields of engineering, complex physical phenomena can be simulated using computer-based simulators. In the field of electrical engineering, SPICE (an acronym for Simulation Program with Integrated Circuit Emphasis) is a massive family of programs written over several decades at the University of California at Berkeley for the simulation of analog, digital, and mixed analog/digital electrical circuits.
SPICE3 (Quarles et al. 1994) is the most recent version of SPICE. SPICE3 performs various types of analysis on circuits containing various circuit elements. The circuit elements include resistors, capacitors, inductors, switches, diodes, transistors, voltage and current sources, transmission lines, and many other devices. SPICE can perform DC analysis, transient analysis, pole-zero analysis, small-signal distortion analysis, sensitivity analysis, noise analysis, AC small-signal analysis, and other types of analysis. The SPICE3 program consists of about 6.1 megabytes of source code spread over 878 separate files that contain approximately 217,000 lines of C source code.
The input to a SPICE simulation consists of a netlist describing the circuit to be analyzed and certain commands that instruct SPICE as to the type of analysis to be performed and the nature of the output to be produced.
Similar simulators exist in many fields of engineering. For example, in the field of mechanical engineering, there are numerous simulators that enable the topological arrangement of various types of physical components (each further specified by different numerical and non-numerical parameters) to be provided to a simulator so that the physical structure can then be simulated.
Automated Circuit Design
Considerable progress has been made in automating certain design problems for purely digital circuits; however, the design of analog circuits and mixed analog-digital circuits has not proved to be as amenable to automation (Rutenbar 1993). In discussing xe2x80x9cthe analog dilemma,xe2x80x9d Aaserud and Nielsen (1995) observe,
xe2x80x9cAnalog designers are few and far between. In contrast to digital design, most of the analog circuits are still handcrafted by the experts or so-called xe2x80x98zahsxe2x80x99 of analog design. The design process is characterized by a combination of experience and intuition and requires a thorough knowledge of the process characteristics and the detailed specifications of the actual product.xe2x80x9d
xe2x80x9cAnalog circuit design is known to be a knowledge-intensive, multiphase, iterative task, which usually stretches over a significant period of time and is performed by designers with a large portfolio of skills. It is therefore considered by many to be a form of art rather than a science.xe2x80x9d
Numerous efforts have been made to automate the design process for analog and mixed analog-digital circuits. Some of these efforts are now described below.
In an interactive design tool for analog integrated circuits called IDAC (Degrauwe 1987), the user begins by selecting various possible topologies for the circuit; IDAC then determines the values of the components in each circuit (in relation to the desired behavioral characteristics); and, the user chooses the best circuit.
In OASYS (Harjani, Rutenbar, and Carley 1989) and OPASYN (Koh, Sequin, and Gray 1990), a topology is chosen beforehand based on heuristic rules and the synthesis tool attempts to size the circuit. If the synthesis tool cannot size the chosen topology correctly, the tool creates a new topology using other heuristic rules and the process continues. The success of these systems depends on the effectiveness of the knowledge base of heuristic rules.
In SEAS (Ning, Kole, Mouthaan, and Wallings 1992), evolution is used to modify the topology and simulated annealing is used to size the circuit.
Maulik, Carley, and Rutenbar (1992) attempt to handle topology selection and circuit sizing simultaneously using expert design knowledge.
Nielsen (1995) has developed a continuous-time filter design tool (his xe2x80x9cC-T compilerxe2x80x9d) that can be used to design analog filter circuits. Nielsen""s process starts with the design, by hand, of a prototype filter. The values of the components and the topology are then adjusted to achieve compliance with the design requirements of the problem at hand.
Genetic Algorithms and Automated Circuit Design
In DARWIN (Kruiskamp and Leenaerts 1995), operational ampliflier (opamp) circuits are designed using the genetic algorithm operating on binary character strings. In creating the initial population in DARWIN, the topology of each opamp in the population is picked randomly from a preestablished hand-designed set of 24 topologies in order to ensure that each circuit in the initial population behaves as an opamp. In addition, a set of problem-specific constraints are solved to ensure that all transistors operate in their proper range and that all transistor sizes lie between maximal and minimal values. The behavior of each opamp is evaluated using a small signal equivalent circuit and analytical calculations specialized to opamp circuits. The fitness of each opamp is computed using a combination of factors, including the deviation between the actual behavior of the circuit and the desired behavior and the power dissipation of the circuit. A crossover operation and mutation operation for the binary chromosome strings describing the opamps are used to create offspring binary chromosome strings.
Hemmi, Mizoguchi, and Shimohara (1994); Higuchi et al. (1993); and Mizoguchi, Hemmi, and Shimohara (1994) have employed genetic methods to the design of digital circuits using a hardware description language (HDL). In these approaches, a grammar is used to drive the development of the design of a digital circuit.
U.S. Patents
U.S. Pat. No. 4,697,242, xe2x80x9cAdaptive Computing System Capable of Learning and Discoveryxe2x80x9d, issued Sep. 29, 1987, Holland et al.
U.S. Pat. No. 4,881,178, xe2x80x9cMethod of Controlling a Classifier System,xe2x80x9d issued Nov. 14, 1989, Holland et al.
U.S. Pat. No. 4,935,877, xe2x80x9cNon-Linear Genetic Algorithms for Solving Problems,xe2x80x9d issued Jun. 19, 1990, Koza.
U.S. Pat. No. 5,136,686, xe2x80x9cNon-Linear Genetic Algorithms for Solving Problems by Finding a Fit Composition of Functions,xe2x80x9d issued Aug. 4, 1992, Koza.
U.S. Pat. No. 5,148,513, xe2x80x9cA Non-Linear Genetic Process for Use with Plural Co-Evolving Populations,xe2x80x9d issued Sep. 15, 1992, Koza, John R., and Rice, James P.
U.S. Pat. No. 5,343,554, xe2x80x9cA Non-Linear Genetic Process for Data Encoding and for Solving Problems Using Automatically Defined Functions,xe2x80x9d issued Aug. 30, 1994, Koza, John R., and Rice, James P.
Other Publications
Aaserud, O. and Nielsen, I. Ring. 1995. Trends in current analog design: A panel debate. Analog Integrated Circuits and Signal Processing. 7(1) 5-9.
Andre, David and Koza, John R. 1996. Parallel genetic programming: A scalable implementation using the transputer architecture. In Angeline, Peter J. and Kinnear, Kenneth E. Jr. (editors). 1996. Advances in Genetic Programming 2. Cambridge, Mass.: The MIT Press.
Darwin, Charles, 1859, On the Origin of Species by Means of Natural Selection, John Murray.
de Garis, Hugo. 1993. Evolvable hardware: Genetic programming of Darwin machines. In International Conference on Neural Networks and Genetic Algorithms. Lecture Notes in Computer Science. Springer-Verlag.
Degrauwe, M. 1987. IDAC: An interactive design tool for analog integrated circuits. IEEE journal of Solid State Circuits. 22:1106-1116.
Gruau, Frederic. 1992a. Cellular Encoding of Genetic Neural Networks. Technical report 92-21. Laboratoire de l""Informatique du Parallxc3xa9lisme. Ecole Normale Supxc3xa9rieure de Lyon. May 1992.
Gruau, Frederic. 1992b. Genetic synthesis of Boolean neural networks with a cell rewriting developmental process. In Schaffer, J. D. and Whitley, Darrell (editors). Proceedings of the Workshop on Combinations of Genetic Algorithms and Neural Networks 1992. Los Alamitos, Calif.: The IEEE Computer Society Press.
Gruau, Frederic. 1993. Genetic synthesis of modular neural networks. In Forrest, Stephanie (editor). Proceedings of the Fifth International Conference on Genetic Algorithms. San Mateo, Calif.: Morgan Kaufinann Publishers Inc. Pages 318-325.
Gruau, Frederic. 1994a. Neural Network Synthesis using Cellular Encoding and the Genetic Algorithm. PhD Thesis. Ecole Normale Supxc3xa9rieure de Lyon.
Gruau, Frederic. 1994b. Genetic micro programming of neural networks. In Kinnear, Kenneth E. Jr. (editor). Advances in Genetic Programming. Cambridge, Mass.: The MIT Press. Pages 495-518.
Harjani, R., Rutenbar, R. A., and Carley, L. R. 1989. OASYS: A framework for analog circuit synthesis. IEEE Transactions on Computer Aided Design. 8:1247-1266.
Hemmi, Hitoshi, Mizoguchi, Jun""ichi, and Shimohara, Katsunori. 1994. Development and evolution of hardware behaviors. In Brooks, Rodney and Maes, Pattie (editors). Artificial Life IV: Proceedings of the Fourth International Workshop on the Synthesis and Simulation of Living Systems. Cambridge, Mass.: The MIT Press. Pages 371-376.
Higuchi, T., Niwa, T., Tanaka, H., Iba, H., de Garis, H. and Furuya, T. 1993. Evolvable hardwarexe2x80x94Genetic-based generation of electric circuitry at gate and hardware description language (HDL) levels. Electrotechnical Laboratory technical report 93-4, Tsukuba, Ibaraki, Japan.
Holland, John H. 1975. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. Ann Arbor, Mich.: University of Michigan Press. Second edition. Cambridge, Mass.: The MIT Press 1992.
Holland, John H. 1986. Escaping brittleness: The possibilities of general-purpose learning algorithms applied to parallel rule-based systems. In Michalski, Ryszard S., Carbonell, Jaime G. and Mitchell, Tom M. Machine Learning: An Artificial Intelligence Approach. Volume II. P. 593-623. Los altos, Calif.: Morgan Kaufmann.
Koh, H. Y., Sequin, C. H. and Gray, P. R. 1990. OPASYN: A compiler for MOS operational amplifiers. IEEE Transactions on Computer Aided Design. 9:113-125.
Koza, John R., 1989. Hierarchical genetic algorithms operating on populations of computer programs, Proceedings of the 11th International Joint Conference on Artificial Intelligence (IJCAI), San Mateo, Calif.: Morgan Kaufmann.
Koza, John R., 1990. Genetic Programming: A Paradigm for Genetically Breeding Populations of Computer Programs to Solve Problems, Stanford University, Dept. of Computer Science, Report No. STAN-CS-90-1314, June 1990.
Koza, John R. 1992. Genetic Programming: On the Programming of Computers by Means of Natural Selection. Cambridge, Mass.: The MIT Press.
Koza, John R. 1994. Genetic Programming II: Automatic Discovery of Reusable Programs. Cambridge, Mass.: The MIT Press.
Koza, John R. 1994b. Architecture-Altering Operations for Evolving the Architecture of a Multi-Part Program in Genetic Programming. Stanford University Computer Science Department technical report STAN-CS-TR-94-1528. Oct. 21, 1994.
Koza, John R., and Rice, James P. 1991. Genetic generation of both the weights and architecture for a neural network. In Proceedings of International Joint Conference on Neural Networks, Seattle, July 1991. Los Alamitos, Calif.: IEEE Press. Volume II. Pages 397-404.
Kruiskamp, Wim and Leenaerts, Domine. 1995. DARWIN: CMOS opamp synthesis by means of a genetic algorithm. Proceedings of the 32nd Design Automation Conference. New York, N.Y.: Association for Computing Machinery. Pages 433-438.
Maulik, P. C. Carley, L. R., and Rutenbar, R. A. 1992. A mixed-integer nonlinear programming approach to analog circuit synthesis. Proceedings of the 29th Design Automation Conference. Los Alamitos, Calif.: IEEE Press, Pages 698-703.
Mizoguchi, Junichi, Hemmi, Hitoshi, and Shimohara, Katsunori. 1994. Production genetic algorithms for automated hardware design through an evolutionary process. Proceedings of the First IEEE Conference on Evolutionary Computation. IEEE Press. Volume I. Pages 661-664.
Nielsen, Ivan Riis. 1995. A C-T filter compilerxe2x80x94From specification to layout. Analog Integrated Circuits and Signal Processing. 7(1):21-33.
Ning, Z., Kole, M., Mouthaan, T., and Wallings, H. 1992. Analog circuit design automation for performance. Proceedings of the 14th IEEE CICC. New York: IEEE Press. Pages 8.2.1-8.2.4.
Prusinkiewicz, Przemyslaw, and Lindenmayer, Aristid. 1990. The Algorithmic Beauty of Plants. New York: Springer-Verlag.
Quarles, Thomas, Newton, A. R., Pederson, D. O., and Sangiovanni-Vincentelli, A. 1994. SPICE 3 Version 3F5 User""s Manual. Department of Electrical Engineering and Computer Science, University of California, Berkeley, Calif. March 1994.
Rutenbar, R. A. 1993. Analog design automation: Where are we? Where are we going? Proceedings of the 15th IEEE CICC. New York: IEEE Press. Pages 13.1.1-13.1.8.
Schaffer, J. D. and Whitley, Darrell (editors). 1992. Proceedings of the Workshop on Combinations of Genetic Algorithms and Neural Networks 1992. Los Alamitos, Calif.: The IEEE Computer Society Press.
A method and apparatus for automated design of complex structures, such as, but not limited to, analog and digital circuits. The present invention operates with a system having a population of entities of various sizes and shapes. Entities in the population comprise constructing actions. The present invention includes a method and apparatus for running an iterative process that creates a design of a structure that satisfies prespecified design goals, in which a series of steps is iterated. In one embodiment, the present invention includes a method and apparatus that iteratively executes constructing actions in entities in the population to develop a structure that has multiple types of components arranged in a topology, where each component is associated with a component value. The present invention also includes a method and apparatus for determining behavior of said developed structure.